
#ifndef _MISC_H_
#define _MISC_H_

#include <stdio.h>
#include <stdarg.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

/**
 * \brief Miscellaneous stuff, which does not fit anywhere else.
 *
 * Actually, the other parts, beginning with ::object, depend on this.
 */
namespace misc {

inline unsigned long get_m_seconds()
{
    return (unsigned long)(clock() / CLOCKS_PER_SEC * 1000);
}

template <class T> inline T min (T a, T b) { return a < b ? a : b; }
template <class T> inline T max (T a, T b) { return a > b ? a : b; }

template <class T> inline T min (T a, T b, T c)
{
   return (min (a, max (b, c)));
}
template <class T> inline T max (T a, T b, T c)
{
   return (max (a, max (b, c)));
}

extern const char *prgName;

void init (int argc, char *argv[]);
void chop (char *s);
char *strip (char *s);


inline void loggingassert (bool cond, const char *format, ...)
{
   if (!cond) {
      fprintf (stderr, "*** [%s] Assertion failed! ***\n", prgName);

      va_list argp;
      va_start (argp, format);
      vfprintf (stderr, format, argp);
      va_end (argp);

      fprintf (stderr, "\n");

      abort ();
   }
}

inline void fail (const char *format, ...)
{
   fprintf (stderr, "*** [%s] Failure! ***\n", prgName);

   va_list argp;
   va_start (argp, format);
   vfprintf (stderr, format, argp);
   va_end (argp);

   fprintf (stderr, "\n");

   abort ();
}

inline void assertNotReached ()
{
   fprintf (stderr, "*** [%s] This should not happen! ***\n", prgName);
   abort ();
}

/**
 * \brief Instances of a sub class of this interface may be compared (less,
 *    greater).
 *
 * Used for sorting etc.
 */
class Comparable
{
public:
    virtual ~Comparable();

   /**
    * \brief Compare two objects c1 and c2.
    *
    * return a value < 0, when c1 is less than c2, a value > 0, when c1
    * is greater than c2, or 0, when c1 and c2 are equal.
    *
    * If also object::Object is implemented, and if c1.equals(c2),
    * c1.compareTo(c2) must be 0, but, unlike you may expect,
    * the reversed is not necessarily true. This method returns 0, if,
    * according to the rules for sorting, there is no difference, but there
    * may still be differences (not relevant for sorting), which "equals" will
    * care about.
    */
   virtual int compareTo(Comparable *other) = 0;

   static int compareFun(const void *p1, const void *p2);
};

/**
 * \brief Simple (simpler than container::untyped::Vector and
 *    container::typed::Vector) template based vector.
 */
template <class T> class SimpleVector
{
private:
   enum {
      /**
       * \brief Edit this for debugging. Should be optimized by the compiler.
       */
      BOUND_CHECKING = 1
   };

   T *array;
   int num, numAlloc;

   inline void resize ()
   {
      if (array == NULL)
         this->array = (T*) malloc (this->numAlloc * sizeof (T));
      if (this->num >= this->numAlloc) {
         while (this->num >= this->numAlloc)
            this->numAlloc <<= 1;
         this->array =
            (T*) realloc(this->array, (this->numAlloc * sizeof (T)));
      }
   }

public:
   inline SimpleVector (int initAlloc)
   {
      this->num = 0;
      this->numAlloc = initAlloc;
      this->array = NULL;
   }

   virtual inline ~SimpleVector ()
   {
      if (this->array)
         free (this->array);
   }

   /**
    * \brief Return the number of elements put into this vector.
    */
   inline int size() { return this->num; }

   inline T* getArray() { return array; }

   /**
    * \brief Increase the vector size by one.
    *
    * May be necessary before calling misc::SimpleVector::set.
    */
   inline void increase() { this->num++; this->resize (); }

   /**
    * \brief Set the size explicitely.
    *
    * May be necessary before called before misc::SimpleVector::set.
    */
   inline void setSize(int newSize) { this->num = newSize; this->resize (); }

   /**
    * \brief Set the size explicitely and initialize new values.
    *
    * May be necessary before called before misc::SimpleVector::set.
    */
   inline void setSize (int newSize, T t) {
      int oldSize = this->num;
      setSize (newSize);
      for (int i = oldSize; i < newSize; i++)
         set (i, t);
   }

   /**
    * \brief Return the reference of one element.
    *
    * \sa misc::SimpleVector::get
    */
   inline T *getRef (int i) {
      if (BOUND_CHECKING)
         loggingassert (i < this->num, "Array index out of bounds: %d >= %d",
                 i, this->num);
      return array + i;
   }

   /**
    * \brief Return the reference of one element.
    *
    */
   inline T get (int i) {
      if (BOUND_CHECKING)
         loggingassert (i < this->num, "Array index out of bounds: %d >= %d",
                 i, this->num);
      return this->array[i];
   }

   /**
    * \brief Store an object in the vector.
    *
    * Unlike in container::untyped::Vector and container::typed::Vector,
    * you have to care about the size, so a call to
    * misc::SimpleVector::increase or misc::SimpleVector::setSize may
    * be necessary before.
    */
   inline void set (int i, T &t) {
      if (BOUND_CHECKING)
         loggingassert (i < this->num, "Array index out of bounds: %d >= %d",
                 i, this->num);
      this->array[i] = t;
   }

   /**
    * \brief Append an object in the vector.
    */
   inline void append (T &t) {
       increase();
       set(num-1, t);
   }
};


/**
 * \brief A class for fast concatenation of a large number of strings.
 */
class StringBuffer
{
private:
   struct Node
   {
      char *data;
      Node *next;
   };

   Node *firstNode, *lastNode;
   size_t numChars;
   char *str;
   bool strValid;

public:
   StringBuffer();
   virtual ~StringBuffer();

   /**
    * \brief Append a NUL-terminated string to the buffer, with copying.
    *
    * A copy is kept in the buffer, so the caller does not have to care
    * about memory management.
    */
   inline void append(const char *str) { appendNoCopy(strdup(str)); }
   void appendNoCopy(char *str);
   const char *getChars();
   void clear ();
};


/**
 * \brief A bit set, which automatically reallocates when needed.
 */
class BitSet
{
private:
   unsigned char *bits;
   int numBytes;

   inline int bytesForBits(int bits) { return bits == 0 ? 1 : (bits + 7) / 8; }

public:
   BitSet(int initBits);
   virtual ~BitSet();
   void intoStringBuffer(misc::StringBuffer *sb);
   bool get(int i);
   void set(int i, bool val);
   void clear();
};

template <class T> class SimpleList
{
public:
    SimpleList() :
        head(NULL),
        tail(NULL),
        curr(NULL),
        list_size(0)
    { }
    virtual ~SimpleList()
    {
        clear();
    }
    void push_back(T &val)
    {
        Node *n = new Node();
        n->data = val;
        n->prev = tail;
        n->next = NULL;
        if (tail != NULL) {
            tail->next = n;
            tail = n;
        } else {
            tail = n;
            head = n;
        }
        list_size++;
    }
    void push_front(T &val)
    {
        Node *n = new Node();
        n->data = val;
        n->prev = NULL;
        n->next = head;
        if (head != NULL) {
            head->prev = n;
            head = n;
        } else {
            head = n;
            tail = n;
        }
        list_size++;
    }
    void pop_back()
    {
        if (this->empty()) {
            throw "List Empty!";
        }
        Node *n = tail;
        if (curr == n) {
            curr = n->prev;
        }
        tail = tail->prev;
        if (tail == NULL) {
            head = NULL;
        }
        delete n;
        list_size--;
    }
    void pop_front()
    {
        if (this->empty()) {
            throw "List Empty!";
        }
        Node *n = head;
        if (curr == n) {
            curr = n->next;
        }
        head = head->next;
        if (head == NULL) {
            tail = NULL;
        }
        delete n;
        list_size--;
    }
    T get_back()
    {
        if (this->empty()) {
            throw "List Empty!";
        }
        return tail->data;
    }
    T get_front()
    {
        if (this->empty()) {
            throw "List Empty!";
        }
        return head->data;
    }
    T iterator_get_next()
    {
        if (this->empty()) {
            throw "List Empty!";
        }
        if (curr == NULL) {
            curr = head;
        } else {
            curr = curr->next;
        }
        if (curr == NULL) {
            throw "reach end of list!";
        }
        return curr->data;
    }
    void iterator_reset()
    {
        curr = NULL;
    }
    int size()
    {
        return list_size;
    }
    inline bool empty() const
    {
        if (head != NULL) {
            return false;
        } else {
            return true;
        }
    }
    void clear()
    {
        Node *n;
        while (head != NULL) {
            n = head;
            head = head->next;
            delete(n);
        }
        tail = NULL;
        curr = NULL;
        list_size = 0;
    }

private:
    struct Node
    {
        T data;
        struct Node *next, *prev;
    };
    struct Node *head, *tail, *curr;
    int list_size;
};

} // namespace misc

#endif // __LOUT_MISC_HH__
